package com.vic.datastructure.leetcode.p4;

/**
 * 什么是斐波那契数列？
 *
 * 斐波那契数列（Fibonacci sequence），又称黄金分割数列，
 * 因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，
 * 指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
 *
 * 简单来说就是，这个数列从第3项开始，每一项都等于前两项之和。
 */
public class Test {

    public static void main(String[] args) {

        // 方法1：递归方法
        test1();

        // 方法2：从下往上计算，使用循环（递归重复计算太多）
        test2();


    }

    /**
     * 方法2
     * 从下往上计算，使用循环（递归重复计算太多）
     */
    private static void test2() {
        System.out.println(Fibonacci2(5));
    }


    public static int Fibonacci2(int n) {
        int[] res = {0, 1};
        if(n < 2) {
            return res[n];
        }
        int first = 0;
        int second = 1;
        int fibn = 0;
        for(int i = 2; i <= n; i++) {
            fibn = first + second;
            first = second;
            second = fibn;
        }
        return fibn;
    }

    /**
     * 方法1
     * 递归方法
     */
    private static void test1() {
        System.out.println(Fibonacci1(5));
    }

    private static int Fibonacci1(int n) {
        if(n == 0) {
            return 0;
        }
        if(n == 1) {
            return 1;
        }

        return Fibonacci1(n - 1) + Fibonacci1(n - 2);
    }



}
